package com.learn.demo.tree;

import java.util.*;

/**
 * 完全二叉树示例
 *
 * @author banjiawei
 * @date 2022/08/17
 */
public class CompleteBinaryTree {

    public static void main(String[] args) {
        Integer[] array = {1,2,3,4,5,6,7,8,9};
        CompleteBinaryTree completeBinaryTreeI = new CompleteBinaryTree();
        completeBinaryTreeI.tree1(array);
    }

    /**
     *
     * @param a int整型一维数组 表示这棵完全二叉树的Bfs遍历序列的结点编号
     * @return long长整型
     */
    public long tree1 (Integer[] a) {
        // write code here
        ComBinTree tree = new ComBinTree(a);
        tree.createBinTree();

        System.out.println("先序遍历");
        tree.preOrderTraverse(tree.getRoot());
        System.out.println();
        System.out.println("中序遍历");
        tree.inOrderTraverse(tree.getRoot());
        System.out.println();
        System.out.println("后序遍历");
        tree.postOrderTraverse(tree.getRoot());
        System.out.println();

        ComBinTree tree1 = new ComBinTree(a);
        tree1.createBinTree();

        System.out.println("BFS宽度优先遍历");
        tree.postOrderTraverse(tree1.getRoot());
        System.out.println();

        System.out.println("DFS深度优先遍历");
        tree.postOrderTraverse(tree1.getRoot());
        System.out.println();

        return 0;
    }



    /**
     * 二叉树内部类
     */
    class ComBinTree {
        /**各个节点*/
        private Integer[] nodeArr;
        /**所有节点*/
        private List<TreeNode> treeNodeList;

        ComBinTree(){}

        ComBinTree(Integer[] nodeArr){
            this.nodeArr = nodeArr;
        }

        public void createBinTree() {
            treeNodeList = new LinkedList<>();
            for (int i = 0; i < nodeArr.length; i++) {
                treeNodeList.add(new TreeNode(nodeArr[i]));
            }
            int lastIndex = nodeArr.length/2-1;
            for (int parentIndex = 0; parentIndex < lastIndex; parentIndex++){
                treeNodeList.get(parentIndex).leftChild = treeNodeList.get(parentIndex*2+1);
                treeNodeList.get(parentIndex).rightChild = treeNodeList.get(parentIndex*2+2);
            }
            // 最后一个节点，单独处理
            treeNodeList.get(lastIndex).leftChild = treeNodeList.get(lastIndex*2+1);
            if(nodeArr.length % 2 != 0){
                treeNodeList.get(lastIndex).rightChild = treeNodeList.get(lastIndex*2+2);
            }
        }

        public TreeNode getRoot(){
            if(Objects.isNull(treeNodeList) || treeNodeList.isEmpty()){
                throw new IllegalArgumentException("请先创建二叉树！");
            }
            return treeNodeList.get(0);
        }

        /**
         * 先序遍历
         * @param root
         */
        public void preOrderTraverse(TreeNode root){
            if(Objects.isNull(root)){
                return;
            }
            System.out.println(root.data +" ");
            preOrderTraverse(root.leftChild);
            preOrderTraverse(root.rightChild);
        }

        /**
         * 中序遍历
         * @param root
         */
        public void inOrderTraverse(TreeNode root){
            if(Objects.isNull(root)){
                return;
            }
            inOrderTraverse(root.leftChild);
            System.out.println(root.data +" ");
            inOrderTraverse(root.rightChild);
        }

        /**
         * 后续遍历
         * @param root
         */
        public void postOrderTraverse(TreeNode root){
            if(Objects.isNull(root)){
                return;
            }
            postOrderTraverse(root.leftChild);
            postOrderTraverse(root.rightChild);
            System.out.println(root.data +" ");
        }

        /**
         * 宽度|广度优先遍历
         * @param root
         */
        public void BFS(TreeNode root){
            if(Objects.isNull(root)){
                return;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()){
                TreeNode head = queue.poll();
                System.out.println(root.data +" ");
                if(!Objects.isNull(head.leftChild)){
                    queue.offer(head.leftChild);
                }
                if(!Objects.isNull(head.rightChild)){
                    queue.offer(head.rightChild);
                }
            }
        }

        public void DFS(TreeNode root){
            if(Objects.isNull(root)){
                return;
            }
            ArrayDeque<TreeNode> stack = new ArrayDeque<>();
            stack.push(root);
            while (!stack.isEmpty()){
                TreeNode head = stack.pop();
                System.out.println(root.data +" ");
                if(!Objects.isNull(head.leftChild)){
                    stack.push(head.leftChild);
                }
                if(!Objects.isNull(head.rightChild)){
                    stack.push(head.rightChild);
                }
            }
        }

    }

    class TreeNode {
        /**左节点*/
        private TreeNode leftChild;
        /**右节点*/
        private TreeNode rightChild;
        /**值*/
        private Integer data;

        TreeNode(Integer data){
            this.data = data;
        }
    }
}
